import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yinsh
 * Date: 2025-03-03
 * Time: 14:32
 */
class Solution {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
  }
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
        Map<Integer,Integer> map = new HashMap<>();
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i],i);
            }
            return myBuildTree(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
        }

        private TreeNode myBuildTree(int[] inorder, int[] postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right) {
            if (inorder_left>inorder_right || postorder_left<postorder_right) return null;
            TreeNode root = new TreeNode(postorder[postorder_right]);
            int gap = map.get(postorder[postorder_right])-inorder_left;
            root.left = myBuildTree(inorder,postorder,inorder_left,inorder_left+gap-1,postorder_left,postorder_left+gap-1);

            root.right = myBuildTree(inorder,postorder,inorder_left+gap+1,inorder_right,postorder_left+gap,postorder_right-1);

            return root;
        }
}
